import math

def int2bin(n, count):
	"""returns the binary of integer n, using count number of digits"""
	return "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])


def f(state, u, n, m):
	"""
	type: p=0,q=1,r=2
	"""
	ret = ""
	for i in range(len(u)):
		if state == 0:
			if u[i] == '0':
				ret += "1"
				state = n-1
			else:
				ret += "0"
				state = m-1
		else:
			ret += u[i]
			state -= 1
	return ret


def step(u, exp, n, m):
	for j in range(len(exp)):
		for i in range(exp[j]):
			u = f(j, u, n, m)
	return u

def test(e1, e2, n, m, max):
	for length in range(1, max + 1):
		for k in range(2 ** length):
			u = int2bin(k, length)
			u1 = step(u, e1, n, m)
			u2 = step(u, e2, n, m)
			if u1 != u2:
				print u, u1, u2, len(u)
				exit()
	print True	

def itertest(n, m, max):
	pass

def gen_coord_table(n, m, length):
	coord_table = {}
	u = int2bin(0, length)
	for a in range(2 ** (length/2 + length % 2)):
		for b in range(2 ** ((length-1)/2 + (length-1) % 2)):
			u1 = step(u, (a,b), n, m)
			coord_table[u1] = (a,b)
	return coord_table

def getcoord(f, n, m, length, coord_table):
	u = int2bin(0, length)
	u1 = step(u, f, n, m)
	return coord_table[u1]

def run_coords(f,n,m,length):
	ans = getcoord(f, n, m, length, gen_coord_table(n,m,length))
	return ans

def test_lens(f, maxlen):
	f = reduce(f)
	for i in range(1, maxlen+1):
		c = run_coords(f, 5,2,i)
		print c
		if c[0] > 0 and c[1] > 0:
			return True
	return False

def reduce(f):
	# assumes f is of length at most 5
	if len(f) != 5:
		return f
	f1 = f
	while f1[0] >= 2 and f1[1] >= 2 and f1[2] >= 1 and f1[3] >= 1 \
		and f1[4] >= 1:
		f1 = (f1[0] - 2, f1[1] - 2, f1[2] - 1, f1[3] - 1, f1[4] - 1)
	return f1

def run_test_lens(max_exp, tolerance):
	for a in range(max_exp):
		for b in range(max_exp):
			for c in range(max_exp):
				for d in range(max_exp):
					for e in range(max_exp):
						f = (a,b,c,d,e)
						r = test_lens(f, tolerance)
						if r == False:
							print f

print test_lens((1,2,0,7,0), 20)

# run_test_lens(10, 10)

# test((4,0), (0,0,0,0,1,9,0,0,0,1,1,0,1), 5, 2, 20)

# print orbittest(5, (1,0,0))

# tester2((1, 3, 0))

# tester()

# cmp("000", (3, 1, 0), (1, 1, 0))

# print orbit("0000", (1, 1, 0))

# cmp("000", (1,1,0), (5,1,0))
